package love_sort

// 归并,递归
func MerSort(nums []int) []int {
	if len(nums) == 1 {
		return nums
	}
	mid := len(nums) / 2

	leftArr := MerSort(nums[:mid])
	rightArr := MerSort(nums[mid:])

	return Merge(leftArr, rightArr)

}

func Merge(left, rigth []int) []int {
	i := 0
	j := 0
	var re []int
	for {
		if i >= len(left) {
			re = append(re, rigth[j:]...)
			break

		}
		if j >= len(rigth) {
			re = append(re, left[i:]...)
			break
		}
		if left[i] < rigth[j] {
			re = append(re, left[i])
			i++
		} else {
			re = append(re, rigth[j])
			j++
		}
	}
	return re

}
